package ch2linkedlist;

import ch2linkedlist.CircularLinkedList.DLListNode;


public class Chapter {
	static ListNode deleteNode(ListNode head, int d) {
		if (head == null) {
			return null;
		}
		
		if (head.val == d) {
			return head.next;
		}
		
		ListNode n = head;
		while (n.next != null) {
			if (n.next.val == d) {
				n.next = n.next.next;
				return head;
			}
			n = n.next;
		}
		
		return null;
	}

	static DLListNode deleteNode(DLListNode head, int d) {
		if (head == null) {
			return null;
		}
		
		if (head.val == d) {
			DLListNode next = (DLListNode) head.next;
			next.prev = null;
			head.next = null;
			return next;
		}
		
		DLListNode n = head;
		while (n.next != null) {
			if (n.next.val == d) {
				DLListNode m = (DLListNode) n.next;
				DLListNode p = (DLListNode) m.next;
				n.next = p;
				if (p != null) {
					p.prev = n;
				}
				m.next = null;
				m.prev = null;
				return head;
			}
			n = (DLListNode) n.next;
		}
		
		return null;
	}
	
	static ListNode insertNode(ListNode head, int d) {
		ListNode node = new ListNode(d);
		node.next = head;
		return node;
	}
	
	static void insertNode(CircularLinkedList list, int d) {
		DLListNode newHead = new DLListNode(d);		
		DLListNode oldHead = (DLListNode) list.sentinel.next;
		newHead.next = oldHead;
		newHead.prev = list.sentinel;
		oldHead.prev = newHead;
		list.sentinel.next = newHead;
	}
	
	public static void print(ListNode head) {
		ListNode n = head;
		while (n != null) {
			System.out.print(n.val);
			System.out.print(" ");
			n = n.next;
		}
		System.out.println();
	}
	
	public static void main(String[] argv) {
		int[] vals = {9, 16, 4, 1};
		ListNode head = createSampleList(vals);

		System.out.println("original: ");
		print(head);
		System.out.println();

//		for (int i=0; i<vals.length; i++) {
//			System.out.println("after removing "+i);
//			head = deleteNode(head, i);
//			
//			print(head);
//			System.out.println();
//		}

		ListNode reverseList = reverseList(head, null);
		print(reverseList);
		
		CircularLinkedList circularLinkedList = new CircularLinkedList(vals);
		insertNode(circularLinkedList, 25);
	}

	static ListNode reverseList(ListNode node, ListNode parent) {
		ListNode next = node.next;
		node.next = parent;
		if (next == null) {
			return node;
		}
		return reverseList(next, node);
	}
	
	public static ListNode createSampleList(int [] vals) {
		int d = 0;
		ListNode head = new ListNode(vals[d]);
		while (d < vals.length-1) {
			d++;
			head.appendToTail(vals[d]);
		}
		return head;
	}
	
}
